|
In graph theory, Vizing's theorem (named for Vadim G. Vizing who published it in 1964) states that the edges of every simple undirected graph may be colored using a number of colors that is at most one larger than the maximum degree of the graph. At least colors are always necessary, so the undirected graphs may be partitioned into two classes: "class one" graphs for which colors suffice, and "class two" graphs for which colors are necessary. ==Examples== When , the graph must itself be a matching, with no two edges adjacent, and its edge chromatic number is one. That is, all graphs with are of class one. When , the graph must be a disjoint union of paths and cycles. If all cycles are even, they can be 2-edge-colored by alternating the two colors around each cycle. However, if there exists at least one odd cycle, then no 2-edge-coloring is possible. That is, a graph with is of class one if and only if it is bipartite. Multigraphs do not in general obey Vizing's theorem. For instance, the multigraph formed by doubling each edge of a triangle has maximum degree four but cannot be edge-colored with fewer than six colors. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Vizing's theorem」の詳細全文を読む スポンサード リンク
|